﻿#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//合并两个有序数组
//给出⼀个有序的整数数组A和有序的整数数组B, 请将数组B合并到数组A中, 变成⼀个有序的升序数组


//解法一
//根据题意可以知道，因为A数组后⾯有⾜够⼤的空间所以我们直接将B数组中的数据添加进A数组后⾯，然后排序

int int_compare(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}

void merge1(int* A, int m, int* B, int n)
{
	memcpy(A + m, B, sizeof(int) * n); //将数组B的内容拷贝到A里面
	qsort(A, m + n, sizeof(int), int_compare);	
}

//解法二
//跳出常规思路中，我们尝试从后往前去⽐较，并且也是将符合要求的数值直接放到数组A中，也是采取的从后往前填充的思想，
// 同时这个也是题⽬要求给定的数组A的空间⼤的原因。

void merge2(int* A, int m, int* B, int n)
{
	int end = m + n - 1;
	int endA = m - 1;
	int endB = n - 1;
	while (end >= 0)
	{
		//由于给定数据范围是- 100~100，所以当下标越界时⽤- 101代替数值，保证下⾯⽐较不受影
		int numA = endA < 0 ? -101 : A[endA];
		int numB = endB < 0 ? -101 : A[endB];
		if (numA > numB)
		{
			A[end--] = A[endA--];
		}
		else
		{
			A[end--] = B[endB--];
		}
	}
}

void Print(int* arr, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	int arr1[11] = { 1,2,3,4,5,6 };
	int arr2[5] = {5,7,8,9,10 };
	int sz1 = sizeof(arr1) / sizeof(arr1[0]);
	/*merge1(arr1, 6, arr2, 5);*/
	//merge2所给方法测试不正确,为什么?
	merge2(arr1, 6, arr2, 5);
	Print(arr1, sz1);
	return 0;
}